//快排，O(nlogn) ,类似选择排序
//快排：也是分治递归思想，计算出分区点（pivot），小于的放前面，大的放后面，找到它的索引，前后再分别排序，
//重点：分区函数（找到分区点索引）   性能：原地排序，不稳定，时间复杂度：平均分的话，就是O（nlogn）,分区点在最前或最后，退化为O（n^2）
const quickSort = (arr, left, right) => {
    if (left < right) {
        let partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1 < left ? left : partitionIndex - 1);
        quickSort(arr, partitionIndex + 1 > right ? right : partitionIndex + 1, right);
    }
}

const partition = (arr, left, right) => {
    let i = left;
    const pivotVal = arr[right];
    for (let j = left; j < right; j++) {
        if (arr[j] < pivotVal) {
            swap(arr, j, i);
            //swap(arr[j],arr[i]);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}


const swap = (arr,i,j)=>{
    const temp = arr[i];
    arr[i]= arr[j];
    arr[j] = temp;
}


// 优化快排：取到好的分区点，最好能分平
// 1、	三数取中法：从首尾中，取出中间值作为分区点，数据再大，可以用五数取中，十数取中法
// 2、	随机法：每次都是随机取一个值，不至于每次最差。
